%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graph-theory-algorithms-book/
%%
%% Copyright (C) 2009--2011 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DontPrintSemicolon
\SetAlgoNoLine
%%
%% input
\KwIn{Two integers $a > 0$ and $b \geq 0$ with $a \geq b$.}
%%
%% output
\KwOut{The greatest common divisor of $a$ and $b$.}
\BlankLine
%%
%% algorithm body
$x \assign a$\;
$y \assign b$\;
\While{$y \neq 0$}{
  $r \assign x \bmod y$\;
  $x \assign y$\;
  $y \assign r$\;
}
\Return $x$
